NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/std/c/719

Internet Message Format | 1996-08-06 | 3.7 KB

Path: inforamp.net!usenet
From: [e-mail] (Peter Curran)
Newsgroups: comp.std.c
Subject: Re: Restrictions on qsort compare function?
Date: Wed, 10 Apr 1996 01:52:07 GMT
Organization: PSC Enterprises
Message-ID: <4kf46j$[e-mail]>
References: <4kbl1l$[e-mail]> <[e-mail]>
Reply-To: [e-mail]
NNTP-Posting-Host: ts47-13.tor.istar.ca
X-Newsreader: Forte Free Agent 1.0.82

Well, I said I was stopping, but . . .

On Tue, 09 Apr 96 16:51:22 GMT in article <[e-mail]>
    Lawrence Kirby <[e-mail]> (Lawrence Kirby) wrote:

<snip>

>Or use rand()! However the relation is defined purely on the values of the
>keys. The standard embodies this idea too -

>"The function shall return an integer less than, equal to, or greater than
> zero if the first argument is considered to be respectively less than, equal
> to, or greater than the second"

>gives no license for the comparison function to consider anything other than
>its arguments in determining the return value. I would certainly accept that
>this is worded badly i.e. "first argument" should read "object pointed to by
>the first argument" and similarly for "second". However this loose usage
>appears elsewhere in the standard and I believe the intent is clear (I'm
>happy to discuss that further).

This implies that looking at a (global) data block to determine, say, what the
current collating sequence is, or whether the user has requested "forward" or
"reverse" ordering, is invalid.  Such a suggestion would certainly contradict my
idea of what constitues a reasonable comparison function.

<snip>

>My argument is based fundamentally on 3.16:

>"Undefined behaviour is otherwise indicated in this International Standard
> by the words ``undefined behaviour'' or by the omission of any explicit
> defintion of behaviour. There is no difference in emphasis among these
> three; they all describe ``behaviour that is undefined.''"

>This means that code has undefined behaviour unless you can show what the
>defined behaviour is according to the standard. In all of your examples
>the behaviour can vary depending on the actual implementation of qsort().
>In the absense of any other limitation in the standard (such as a statement
>of implementation-defined behaviour), this means the behaviour is undefined.

>To disprove my assertion for any of your examples the bottom line is to
>show, by reference to the standard, what the defined behaviour is. An
>example is putting forward a reasonable definition of 'sort' which would
>make the example well defined.

I have described comparison functions that return values that appropriately
reflect what I said I consider to be the relative order of the values passed to
them.  This is what the standard says they must do, and they do it.  I do not
see any reason to consider undefined behaviour to have been invoked.  (I do see
it possible when the values of the (pointer) parameters are taken into account
in the function, as I explained earlier, but I am not convinced that the
comparison function can be held responsible, based on the standard.)

>Something else to consider is that the bsearch() function defines a
>comparison function in essentially the same way as the qsort() function
>does (except that it refers correctly to the key object and array element
>rather than just 'arguments'), so a valid qsort() comparison function
>ought to be a valig bsearch() comparison function.

Agreed - the details of value/pointer-to-value text in the standard should be
corrected, but it is not germane to the discussion here - I am assuming the
obvious intent.

--
Peter Curran                               [e-mail]